import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class MergeSortedLists {

    public static List<Integer> merge(List<Integer> list1, List<Integer> list2) {
        int i = 0, j = 0;
        List<Integer> mergedList = new ArrayList<>();

        // 当两个列表都有剩余元素时，比较并合并
        while (i < list1.size() && j < list2.size()) {
            if (list1.get(i) <= list2.get(j)) {
                mergedList.add(list1.get(i++));
            } else {
                mergedList.add(list2.get(j++));
            }
        }

        // 如果有剩余的元素，直接追加到结果列表
        while (i < list1.size()) {
            mergedList.add(list1.get(i++));
        }
        while (j < list2.size()) {
            mergedList.add(list2.get(j++));
        }

        return mergedList;
    }

    public static void main(String[] args) {
        List<Integer> list1 = Arrays.asList(1, 4, 6, 76, 89);
        List<Integer> list2 = Arrays.asList(23, 56, 87, 123);

        List<Integer> mergedList = merge(list1, list2);
        System.out.println(mergedList);
        // 输出: [1, 4, 6, 23, 56, 76, 87, 89, 123]
    }
}
